МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота № 2
Асимптотичні характеристики складності алгоритму;
алгоритми з поліноміальною та експоненціальною складністю. з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
1. МЕТА РОБОТИ
Ознайомитись з асимптотичними характеристиками складності
та класами складності алгоритмів.
ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Часова складність.
В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм
повинен задовільняти вимогам, які часом суперечать одна одній:
бути простим для розуміння, переводу в програмний код, відлагодження.
ефективно використовувати комп'ютерні ресурси і виконуватись швидко.
Якщо програма повинна виконуватись декілька разів, то перша вимога більш
важлива. Вартість робочого часу програміста перевищує вартість машинного часу
виконання програми, тому вартість програми оптимізується по вартості написання, а не
виконання програми. Якщо задача вимагає значних обчислювальних витрат, то вартість
виконання програми може перевищити вартість написання програми, особливо коли
програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку
реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш
складна програма.
На час виконання програми впливають наступні чинники:
ввід інформації в програму;
якість скомпільованого коду;
машинні інструкції, які використовуються для виконання програми;
часова складність алгоритму(ЧС).
Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від
самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для
інших – від їх "розміру" (задачі сортування).
Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку,
тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для
цього алгоритму.
Використовується також ЧС в середньому випадку (в статистичному сенсі), як
середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в
середньому випадку важче визначити ніж ЧС для найгіршого випадку, через те що це
математично важка для розв'язання задача. Крім того, іноді важко визначити, що означає
"середні" вхідні дані.
Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання
цієї функції. Код програми
// don't forget to use compilation key for Linux: -lm
#define _CRT_SECURE_NO_WARNINGS // for using fopen in VS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#ifndef UINT
#define UINT unsigned long int
#endif
#ifndef USHORT
#define USHORT unsigned short
#endif
#ifndef UCHAR
#define UCHAR unsigned char
#endif
#define QDBMP_VERSION_MAJOR 1
#define QDBMP_VERSION_MINOR 0
#define QDBMP_VERSION_PATCH 1
typedef enum
{
BMP_OK = 0,
BMP_ERROR,
BMP_OUT_OF_MEMORY,
BMP_IO_ERROR,
BMP_FILE_NOT_FOUND,
BMP_FILE_NOT_SUPPORTED,
BMP_FILE_INVALID,
BMP_INVALID_ARGUMENT,
BMP_TYPE_MISMATCH,
BMP_ERROR_NUM
} BMP_STATUS;
typedef struct _BMP BMP;
BMP* BMP_Create(UINT width, UINT height, USHORT depth);
void BMP_Free(BMP* bmp);
BMP* BMP_ReadFile(const char* filename);
void BMP_WriteFile(BMP* bmp, const char* filename);
UINT BMP_GetWidth(BMP* bmp);
UINT BMP_GetHeight(BMP* bmp);
USHORT BMP_GetDepth(BMP* bmp);
void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b);
void BMP_GetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR* val);
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val);
void BMP_GetPaletteColor(BMP* bmp, UCHAR index, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b);
BMP_STATUS BMP_GetError();
const char* BMP_GetErrorDescription();
#define PALETTE_SIZE 256
#define OUTPUT_WIDTH 512
#define OUTPUT_HEIGHT 512
#define RECTANGLE...
